﻿#include<stdio.h>
#include"state.h"

void creatRand(SortElem *s,long n, long j){
	long i = 0, a;
	srand((unsigned)time(NULL)+j);
	while(i < n){
		a = rand();
		s[i].key = a;
		s[i].otherData = a;
		i++;
	}
}
void setSame(SortElem *s, SortElem *s1, long n){
	long i = 0;
	while(i<n){
		s[i].key=s1[i].key;
		s[i].key=s1[i].otherData;
		i++;
	}
}
/*
 * 冒泡法排序
 * s为待排数组，n为数组长度，
 * cmpTime为比较次数，mvTime为移动元素次数。
 */
void bubbleSort(SortElem *s, long n, long *cmpTime, long *mvTime){
	SortElem t;
	long i,j;
	*mvTime = 0;
	*cmpTime = 0;
	for(i=0;i<n;i++){
		for(j=1;j<n-i;j++){
			*cmpTime+=1;
			if(s[j-1].key>s[j].key){
				*mvTime+=3;
				t=s[j-1];
				s[j-1]=s[j];
				s[j]=t;
			}
		}
	}
}
/*
 * 直接插入法排序
 * s为待排数组，n为数组长度，
 * cmpTime为比较次数，mvTime为移动元素次数。
 */
void dirInsertSort(SortElem *s, long n, long *cmpTime, long *mvTime){
	SortElem t;
	long i,j;
	*mvTime = 0;
	*cmpTime = 0;
	for(i=1; i<n;i++){
		*cmpTime+=1;
		if(s[i].key<s[i-1].key){
			t=s[i];
			*mvTime+=1;
			for(j=i-1; t.key<s[j].key; j--){
				*cmpTime+=1;
				*mvTime+=1;
				s[j+1]=s[j];
			}
			s[j+1]=t;
			*mvTime+=1;
		}
	}
}

/*
 * 折半直接插入法排序
 * s为待排数组，n为数组长度，
 * cmpTime为比较次数，mvTime为移动元素次数。
 */
void dirInsertSort2(SortElem *s, long n, long *cmpTime, long *mvTime){
	SortElem t;
	long i,j,low,high,m;
	*mvTime = 0;
	*cmpTime = 0;
	for(i=1;i<n;i++){
		t=s[i];
		*mvTime+=1;
		low=0; high=i-1;
		while(low<=high){
			m=(low+high)/2;
			*cmpTime+=1;
			if(t.key<s[m].key)
				high=m-1;
			else low=m+1;
		}
		for(j=i-1;j>=high+1;--j){
			*mvTime+=1;
			s[j+1]=s[j];
		}
		s[high+1]=t;
		*mvTime+=1;
	}
}
/*
 * 简单选择排序
 * 将第i个数与（i+1，n）数比较，若大则交换
 * 得到的每个i都是i到n之间最小的
 * s为待排数组，n为数组长度，
 * cmpTime为比较次数，mvTime为移动元素次数。
 */
void eaSelectSort(SortElem *s, long n, long *cmpTime, long *mvTime){
	long i,j;
	SortElem t;
	*mvTime=0;
	*cmpTime = 0;
	for(i=0; i < n-1; i++)
		for(j = i+1; j<n; j++){
			*cmpTime+=1;
			if(s[i].key>s[j].key){
				*mvTime+=3;
				t=s[i];
				s[i]=s[j];
				s[j]=t;
			}
		}
}
/*
 * 改进的简单选择排序
 * 将第i个数与（i+1，n）数比较，若大则交换
 * 每次比较只是记录下序号
 * 得到的每个i都是i到n之间最小的
 * s为待排数组，n为数组长度，
 * cmpTime为比较次数，mvTime为移动元素次数。
 */
void eaSelectSort2(SortElem *s, long n, long *cmpTime, long *mvTime){
	long i,j,min;
	SortElem t;
	*mvTime = 0;
	*cmpTime = 0;
	for(i=0; i < n-1; i++){
		min=i;
		for(j = i+1; j<n; j++){
			*cmpTime+=1;
			if(s[min].key>s[j].key)
				min=j;
		}
		t=s[i];
		s[i]=s[min];
		s[min]=t;
		*mvTime+=3;
	}
}

/*
 * 假设s[i]到s[j]除s[i]外均满足堆的定义
 * 函数调整s[i]到s[j]使其成为一个大顶堆
 * s为待排数组
 */
void heapAdjust(SortElem *s, long i, long m, long *cmpTime, long *mvTime){
	SortElem t=s[i];
	long j;
	for(j=2*i+1; j<=m; j=j*2+1){
		*cmpTime += 2;
		if(j<m&&s[j].key<s[j+1].key)	j++;
		if(t.key>s[j].key)	break;
		s[i]=s[j];
		i=j;
		*mvTime+=1;
	}
	s[i]=t;
	*mvTime+=1;
}

void heapSort(SortElem *s, long n, long *cmpTime, long *mvTime){
	long i;
	SortElem t;
	*cmpTime = 0;
	*mvTime = 0;
	for(i = (n-2)/2; i>=0; i--)
		heapAdjust(s, i, n-1, cmpTime, mvTime);
	for(i = n-1; i>0; i--){
		t=s[0];
		s[0]=s[i];
		s[i]=t;
		*mvTime+=3;
		heapAdjust(s,0,i-1,cmpTime, mvTime);
	}
}

long partition(SortElem *s, long low, long high, long *cmpTime, long *mvTime){
	SortElem t=s[low];
	long pivotkey=s[low].key;
	while(low<high){
		while(low<high&&s[high].key>=pivotkey){
			--high;
			*cmpTime+=1;
		}
		s[low]=s[high];
		while(low<high&&s[low].key<=pivotkey) {
			++low;
			*cmpTime+=1;
		}
		s[high]=s[low];
		*mvTime+=2;
	}
	s[low]=t;
	*mvTime+=2;
	return low;
}

void qSort(SortElem *s, long low, long high, long *cmpTime, long *mvTime){
	long pivotloc;
	if(low<high){
		pivotloc = partition(s,low,high,cmpTime,mvTime);
		qSort(s,low,pivotloc-1,cmpTime,mvTime);
		qSort(s,pivotloc+1,high,cmpTime,mvTime);
	}
}

void quickSort(SortElem *s, long n, long *cmpTime, long *mvTime){
	*cmpTime = 0;
	*mvTime = 0;
	qSort(s,0,n-1,cmpTime,mvTime);
}
